#ifndef HEAP_H
#define HEAP_H

#include "Vector.h"
#include <iostream>
using std::cin;
using std::cout;
template <class T>
class Heap //这是一个小根堆
{
    Vector<T> vec;
    int size;
    void BuildHeap();
    void PercolateDown(int h);
    void PercolateUp();

public:
    Heap(int max = 100) : vec(max), size(0) {}
    Heap(const Vector<T> &vt);
    bool Empty() const
    {
        return size == 0;
    }
    int Size()
    {
        return size;
    }

    void Insert(const T &item);
    const T &Top() const
    {
        return vec[0];
    }
    void DeleteMin();
    void DeleteMin(T &item);
    void Clear()
    {
        size = 0;
    }
    void print()
    {
        vec.print();
    }
};

template <class T>
void Heap<T>::PercolateDown(int h) //对h位置heapify
{
    int p = h, c = 2 * p + 1;
    T temp = vec[p];
    while (c < size)
    {
        if (c + 1 < size && vec[c + 1] < vec[c])
            ++c;
        if (temp < vec[c])
            break;
        else
        {
            vec[p] = vec[c];
            p = c;
            c = 2 * p + 1;
        }
    }
    vec[p] = temp;
}
template <class T>
void Heap<T>::PercolateUp() //向上调整堆，用于插入操作
{
    int c = size - 1, p = (c - 1) / 2;
    T temp = vec[c];
    while (c > 0)
        if (vec[p] <= temp)
            break;
        else
        {
            vec[c] = vec[p];
            c = p;
            p = (c - 1) / 2;
        }
    vec[c] = temp;
}

template <class T>
void Heap<T>::BuildHeap(void)
{
    for (int i = size / 2 - 1; i >= 0; i--)
        PercolateDown(i);
}

template <class T>
Heap<T>::Heap(const Vector<T> &vt)
// : vec(vt.Size() + 10), size(vt.Size())
{
    // for (int i = 0; i < size; ++i)
    //     vec[i] = vt[i];
    vec = vt;
    size = vt.Size();
    BuildHeap();
}

template <class T>
void Heap<T>::Insert(const T &item)
{
    if (size == vec.Size())
        vec.Resize(vec.Size() * 2);
    vec[size] = item;
    size++;
    PercolateUp();
}
template <class T>
void Heap<T>::DeleteMin(void)
{
    if (size == 0)
    {
        cout << "Heap empty!";
        exit(1);
    }
    vec[0] = vec[size - 1];
    size--;
    PercolateDown(0);
}
template <class T>
void Heap<T>::DeleteMin(T &item) //删除堆顶元素，把元素返回到item之中
{
    if (size == 0)
    {
        cout << "Heap empty!";
        exit(1);
    }
    item = vec[0];
    vec[0] = vec[size - 1];
    size--;
    PercolateDown(0);
}

#endif
